Canadians create unbeatable computer at checkers   

July 20, 2007

WASHINGTON --  It took 18 years to figure out all 500 billion billion combinations at checkers, but Canadian scientists have finally programmed a computer that cannot be beat at the 5,000-year-old game.

The achievement, reported Thursday in Science magazine's latest issue, is considered a milestone in the development of artificial intelligence.

Called Chinook, the checkers champion computer is the brainchild of Jonathan Schaeffer and his team of computer wizards at the University of Alberta.

Completed in April, Chinook can never be beaten, and can only be tied at checkers if its opponent makes all the right moves, Schaeffer said.

"I think we've raised the bar, and raised it quite a bit, in terms of what can be achieved in computer technology and artificial intelligence," said Schaeffer, who chairs the university's Department of Computing Science.

"With Chinook, we've pushed the envelope about 1 million times more than anything that's been done before."

A self-described "awful" checkers player, Schaeffer created Chinook to exploit the superior processing and memory capabilities of computers and determine the best way to incorporate artificial intelligence principles in order to play checkers.

He consulted the world's top checkers players in developing the program and over 18 years ran an average of 50 computers - with more than 200 running at peak times - daily to compute the knowledge necessary to complete Chinook, albeit an interruption from 1997-2001.

Schaeffer said that the initial goal of the project was to have Chinook conquer the world championship in checkers. It entered in 1990, reached the finals in 1992 but lost, and in 1994 became the first computer to take the championship.

Chinook plays by English draughts rules, also called international rules, with an 8x8 board - not the Canadian variation with a 12x12 board.

Chinook has its own entry in the Guinness Book of Records. It remained undefeated until 1997 when it was "retired."

But Schaeffer did not stop there and in 2001 began tweaking Chinook to make it completely unbeatable at the board game.

"I'm thrilled with this achievement," he said. "Solving checkers has been something of an obsession of mine for nearly two decades, and it's really satisfying to see it through to its conclusion."

At chess, however, computers have a long way to go - centuries scientists estimate - before they can handle the astronomical combinations required to master the game to the point of perfection.

Checkers boards have been found in Egyptian archaeological excavations.